#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <mpi.h>
#include <math.h>
#include <omp.h>
#include <time.h>

#define WORD_SIZE 7
#define N_WORDS   5800000
#define RATE 100

/* Estrutura para aramzenar as palavras do arquivo, evitando que se encontre
 * novamente uma palavra ja encontrada */
typedef struct {
    char string[WORD_SIZE];
    int enable;
} Word;


int create_words_list(Word *words_list, FILE *f, int seek, int block_size);
int palavraRandomica(char *word);
int search_word(char *word, Word *list, int list_size);
int is_equal(char *w1, Word *w2);

int main(int argc, char *argv[]){
    int node_number;
    int n_nodes;
    MPI_Status Stat;
    Word *words_list;
    FILE *f = fopen("filtrado2.txt", "r");
    int file_size;
    int block_size;
    int seek_begin;
    int seek_end;
    int list_size = 0;
    int words_list_size;
    char word[WORD_SIZE];
    int word_size;
    int source = 0;
    int destination;
    int finish = 0;
    int n_words = 0;
    int n_found = 0;
    int n_found_node = 0;
    int total_found = 0;
    int rate;
    int run_time;
    int i;
    time_t start, actual;
    FILE *res = fopen("result.txt", "w");

    srand(time(NULL));
    start = time(NULL); /* marca o inicio da execucao do programa */

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &node_number); /*Obtem o numero da Node*/
    MPI_Comm_size(MPI_COMM_WORLD, &n_nodes); /*obtem o nro de nodes*/
    
    /* cada no, com excecao do nro 0, gera uma lista com as palavras
     * de um bloco do arquivo */
    if(node_number) {
        /* calcula o tamanho do arquivo de texto */
        fseek(f, 0, SEEK_END);
	file_size = ftell(f);
	/* retorna o cursor para o inicio do arquivo */
	rewind(f);
	/* calcula o tamanho aproximado do bloco do arquivo que cada no
	 * vai trazer para memoria */
	block_size =  (int) ceil( ((float) file_size) / (n_nodes - 1) );
	/* marca a posicao inicial e final do arquivo dentro das quais cada no deve
	 * ler o arquivo */
	seek_begin = (node_number - 1) * block_size;
	seek_end = seek_begin + block_size;
	/* o ultimo no nao deve tentar ler alem do tamanho do arquivo, para evitar 
	 * a leitura de lixos */
	if(seek_end >= file_size) {
	    seek_end = file_size - 1;
	}
	/* calcula o nro de palavras aproximado que cada no vai armazenar,
	 * de acordo com o nro total de palavras no arquivo e o nro de nos,
	 * deste modo garante-se que um vetor de tamanho suficiente seja 
	 * alocada para a lista de palavras */
	words_list_size = N_WORDS / (n_nodes - 1);
	/* lista para armazenar as palavras de um bloco do arquivo */
	words_list = (Word*) malloc(words_list_size * sizeof(Word));
	/* cria a lista com as palavras do bloco de arquivo lido */
	list_size = create_words_list(words_list, f, seek_begin, seek_end);
    }
    
    /* aramzena em n_words, do no zero, o nro total de palavras no arquivo */
    destination = 0;
    MPI_Reduce(&list_size, &n_words, 1, MPI_INT, MPI_SUM, destination, MPI_COMM_WORLD);
 
    /* no zero trasmite aos outros o nro total de palavras no arquivo. Todos
     * os nos vao usar este valor para verificar se a execucao do programa chegou ao fim */
    if(node_number == 0) {
	actual = time(NULL);
	printf("Tempo para carregar o arquivo na memoria: %f\n\n", difftime(actual, start));   
	fprintf(res, "Tempo para carregar o arquivo na memoria: %f\n\n", difftime(actual, start));   
	fflush(res);
	for(i = 1; i < n_nodes; i++) {
	    MPI_Send(&n_words, 1, MPI_INT, i, 1, MPI_COMM_WORLD); 
	}
    } else {
	MPI_Recv(&n_words, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &Stat);
    }

    rate = 10; /* variavel para marcacao do tempo, de acordo com a porcentagem encontrada */ 
    do {
        /* looping principal: em cada iteracao, o no nro zero gera uma palavra aleatoria e
	 * envia para todos os outros nos. Estes executam uma busca sequencial desta palvara
	 * em suas respectivas listas. Ao final da busca, estes nos enviam para o no nro 
	 * zero o nro de vezes que a palavra procurada aparece em suas listas (lembrando
	 * que existem palavras repetidas). A soma dos valores enviados pelos nos de busca
	 * eh realizada no no nro zero por reducao, mantendo a consistencia. Quando uma 
	 * palavra eh encontrada na lista, ela eh desabilitada para que nas proximas iteracoes
	 * ela nao possa ser encontrada novamente.  */
	if(node_number == 0){
	    word_size = palavraRandomica(word); /* gera uma palavra aleatorioa */
	    /* envia a palavra gerada para os outros nos */
	    for(i = 1; i < n_nodes; i++) {
		destination = i;
		MPI_Send(&word_size, 1, MPI_INT, destination, 1, MPI_COMM_WORLD);
		MPI_Send(word, word_size + 1, MPI_CHAR, destination, 1, MPI_COMM_WORLD);
	    }
	}  else {
	    /* recebe a palavra enviada pelo no 0 */
	    MPI_Recv(&word_size, 1, MPI_INT, source, 1, MPI_COMM_WORLD, &Stat);
	    MPI_Recv(word, word_size + 1, MPI_CHAR, source, 1, MPI_COMM_WORLD, &Stat);
	    /* verifica quantas vezes a palavra eh encontrada na lista de palavras do no */
	    n_found_node = search_word(word, words_list, list_size);
	}
	
	/* o no nro zero recebe a soma do nro de palavras que cada no encontrou em 
	 * suas respectivas listas */
	MPI_Reduce(&n_found_node, &n_found, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
	
	if(node_number == 0) {
	    /* atualiza o nro de palavras total encontradas ate o momento */
	    total_found += n_found;  
	    /* imprime na saida padrao as palavras encontradas */
	    if(n_found) printf("%s - total encontrado: %d\n", word, total_found);
	    /* envia o total de palavras encontradas ate o momento para os outros nos */
	    for(i = 1; i < n_nodes; i++) {		
		MPI_Send(&total_found, 1, MPI_INT, i, 1, MPI_COMM_WORLD); 
	    }
	    /* imprime no arquivo e na saida padrao o tempo de execucao cada vez uma 
	     * uma porcentagem especifica de palavras encontradas eh atingida. A 
	     * porcentagem inicial eh 10, e esta eh incrementada de 10 em 10 */
	    if( ( (total_found * 100) / n_words ) >= rate ) {
	        actual = time(NULL);
	        printf("porcentagem: %d\ntempo: %f\n\n", rate, difftime(actual, start));
		fprintf(res, "porcentagem: %d\ntempo: %f\n\n", rate, difftime(actual, start));
		fflush(res);
	        rate += 10;	 
	    }
	} else {
	    /* ros nos de busca recebem o total de palavras encontradas ate o momento */
	    MPI_Recv(&total_found, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &Stat);
	}
	/* ao encontrar 100% (RATE) das palavras do arquivo, todos os nos saem do looping */
    } while( ( (total_found * 100) / n_words ) <= RATE ); 
    
    MPI_Finalize();
    return 0;
}


/*
 * Cria uma lista do tipo Word com as palavras lidas em um bloco de um arquivo.
 * @ENTRADA:
 *  - *f: ponteiro para o arquivo cujo bloco se quer ler
 *  - seek_begin: posicao no arquivo que marca o inicio do bloco que
 *                se quer ler
 *  - seek_end: posicao no arquivo que marca o final do bloco que se
 *              quer ler
 * @SAIDA:
 *  - *words_list: vetor do tipo Word para armazenar a lista lida no bloco 
 *                 do arquivo
 * @RETORNO:
 *  - int: nro de palavras inseridas na lista
 */
int create_words_list(Word *words_list, FILE *f, int seek_begin, int seek_end) {
    int i;
    char c;
    long int current_pos;
    
    fseek(f, seek_begin, SEEK_SET);
    
    if(seek_begin) {
	do {
	    fscanf(f, "%c", &c);
	} while(c != '\n');
    }
    
    i = 0;
    current_pos = ftell(f);
    while (current_pos < seek_end) {
	fscanf(f, "%s", words_list[i].string);
	words_list[i].enable = 1;
	current_pos = ftell(f);
	i++;
    }
    
    return i;
}

/*
 * Gera uma palavra de tamanho aleatorio (entre 1 e 5), cujo letras
 * tambem sao geradas aleatoriamente.
 * @SAIDA:
 *  - *string: vetor do tipo char para armazenar a palavra gerada 
 * @RETORNO:
 *  - int: tamanho da palavra gerada
 */
int palavraRandomica(char *string){
    char c;
    int i;
    int tam;
    
    tam = 1 + rand()%5;
    
    for(i=0; i<tam;i++){
	c = 97 + rand()%26;
		string[i]=c;	
    }
    string[i]='\0';

    return tam;
}

/*
 * Executa uma busca sequencial pelas ocorrencias de uma palavra
 * na lista de palavras. A busca eh paralelizada utilizando-se
 * openmp.
 * @ENTRADA:
 *  - word[]: palavra procurada
 *  - *list: lista na qual se deseja procurar as palavras
 *  - list_size: tamanho da lista
 * @RETORNO:
 *  - int: nro de ocorrencias da palavra procurada na lista
 */
int search_word(char word[], Word *list, int list_size) {
    int i;
    int equals;
    int n_found = 0;

    #pragma omp parallel firstprivate(n_found) reduction(+:equals)
    {
    
        #pragma omp for schedule(dynamic)
        for(i = 0; i < list_size; i++) {
	    if(list[i].enable && is_equal(word, &list[i])) {
	        n_found++;
	    }
	}
	equals = n_found;
    }
    return equals;
}


/*
 * Compara uma string com a string presente em um estrutura 
 * Word. Se as strings forem identicas, desabilita a estrutura
 * para que esta nao seja contabilizada novamente em um busca 
 * posterior.
 * @ENTRADA:
 *  - w1[]: string que se quer comparar com uma estrutura Word
 *  - w2[]: estrutura Word que se quer comparar com uma string
 * @SAIDA:
 *  - w2[]: se iguais, a estrutura eh desabilitada (w2->enable = 0)
 * @RETORNO
 *  - int: se as strings forem iguais, retorna 1. Caso contrario retorna 0
 */
int is_equal(char w1[], Word *w2) {
    if(!strcmp(w1,w2->string)) {
	w2->enable = 0;
	return 1;
    } else {
	return 0;
    }
}
